large_numbersfandomcom-20200214-history
Fibonacci prime
A Fibonacci prime is a Fibonacci number that is prime, a type of integer sequence prime. The first Fibonacci primes are : :2, 3, 5, 13, 89, 233, 1597, 28657, 514229, 433494437, 2971215073, .... Known Fibonacci primes It is not known whether there are infinitely many Fibonacci primes. With the indexing starting with , the first 34 are ''Fn'' for the ''n values : :n'' = 3, 4, 5, 7, 11, 13, 17, 23, 29, 43, 47, 83, 131, 137, 359, 431, 433, 449, 509, 569, 571, 2971, 4723, 5387, 9311, 9677, 14431, 25561, 30757, 35999, 37511, 50833, 81839, 104911. In addition to these proven Fibonacci primes, there have been found probable primes for :''n = 130021, 148091, 201107, 397379, 433781, 590041, 593689, 604711, 931517, 1049897, 1285607, 1636007, 1803059, 1968721, 2904353, 3244369.PRP Top Records, Search for : F(n). Retrieved 2017-03-03. Except for the case n'' = 4, all Fibonacci primes have a prime index, because if ''a divides b'', then F_a also divides F_b , but not every prime is the index of a Fibonacci prime. ''Fp'' is prime for 8 of the first 10 primes ''p; the exceptions are F''2 = 1 and ''F''19 = 4181 = 37 × 113. However, Fibonacci primes become rarer as the index increases. ''Fp'' is prime for only 26 of the 1,229 primes ''p below 10,000.Sloane's , The number of prime factors in the Fibonacci numbers with prime index are: :0, 1, 1, 1, 1, 1, 1, 2, 1, 1, 2, 3, 2, 1, 1, 2, 2, 2, 3, 2, 2, 2, 1, 2, 4, 2, 3, 2, 2, 2, 2, 1, 1, 3, 4, 2, 4, 4, 2, 2, 3, 3, 2, 2, 4, 2, 4, 4, 2, 5, 3, 4, 3, 2, 3, 3, 4, 2, 2, 3, 4, 2, 4, 4, 4, 3, 2, 3, 5, 4, 2, 1, ... , the largest known certain Fibonacci prime is F''104911, with 21925 digits. It was proved prime by Mathew Steine and Bouk de Water in 2015.Chris Caldwell, The Top Twenty: Fibonacci Number from the Prime Pages. Retrieved 2017-03-03. The largest known probable Fibonacci prime is ''F''3244369. It was found by Henri Lifchitz in 2017. It was shown by Nick MacKinnon that the only Fibonacci numbers that are also members of the set of prime twins are 3, 5 and 13.N. MacKinnon, Problem 10844, Amer. Math. Monthly 109, (2002), p. 78 Divisibility of Fibonacci numbers A prime p \neq 5 divides F_{p-1} if and only if ''p is congruent to ±1 modulo 5, and p'' divides F_{p+1} if and only if is congruent to ±2 modulo 5. (For ''p = 5, F''5 = 5 so 5 divides ''F''5) Fibonacci numbers that have a prime index ''p do not share any common divisors greater than 1 with the preceding Fibonacci numbers, due to the identity:Paulo Ribenboim, My Numbers, My Friends, Springer-Verlag 2000 : \gcd(F_n, F_m) = F_{\gcd(n,m)}, which implies the infinitude of primes. For , Fn divides Fm iff n'' divides ''m.Wells 1986, p.65 If we suppose that m'' is a prime number ''p, and n'' is less than ''p, then it is clear that F''p'', cannot share any common divisors with the preceding Fibonacci numbers. : \gcd(F_p, F_n) = F_{\gcd(p,n)} = F_1 = 1. This means that Fp will always have characteristic factors or be a prime characteristic factor itself. The number of distinct prime factors of each Fibonacci number can be put into simple terms. * F''nk'' is a multiple of F''k'' for all values of n and k from 1 up.The mathematical magic of Fibonacci numbers Factors of Fibonacci numbers It's safe to say that Fnk will have "at least" the same number of distinct prime factors as Fk. All F''p'' will have no factors of F''k'', but "at least" one new characteristic prime from Carmichael's theorem. * Carmichael's Theorem applies to all Fibonacci numbers except 4 special cases: F_1 =F_2 =1, F_6 = 8 and F_{12} = 144. If we look at the prime factors of a Fibonacci number, there will be at least one of them that has never before appeared as a factor in any earlier Fibonacci number. Let πn be the number of distinct prime factors of Fn. ::If k'' | ''n then \pi_n \geqslant \pi_k +1 except for \pi_6 = \pi_3 =1. ::If k'' = 1, and ''n is an odd prime, then 1 | p'' and \pi_p \geqslant \pi_1 +1 = 1. The first step in finding the characteristic quotient of any ''Fn is to divide out the prime factors of all earlier Fibonacci numbers Fk for which k'' | ''n.Jarden - Recurring sequences, Volume 1, Fibonacci quarterly, by Brother U. Alfred The exact quotients left over are prime factors that have not yet appeared. If p'' and ''q are both primes, then all factors of Fpq are characteristic, except for those of Fp and Fq. : \begin{align} \gcd (F_{pq}, F_q ) &= F_{\gcd(pq, q)} = F_q \\ \gcd (F_{pq}, F_p ) &= F_{\gcd(pq, p)} = F_p \end{align} Therefore: : \pi_{pq} \geqslant \begin{cases} \pi_p + \pi_q + 1 & p\neq q \\ \pi_p + 1 & p = q \end{cases} The number of distinct prime factors of the Fibonacci numbers with a prime index is directly relevant to the counting function. Rank of Apparition For a prime p'', the smallest index ''u > 0 such that Fu is divisible by p'' is called the '''rank of apparition' (sometimes called Fibonacci entry point) of p'' and denoted ''a(p''). The rank of apparition ''a(p'') is defined for every prime ''p. The rank of apparition divides the Pisano period π(p'') and allows to determine all Fibonacci numbers divisible by ''p. For the divisibility of Fibonacci numbers by powers of a prime, p \geqslant 3, n \geqslant 2 and k \geqslant 0 : p^n \mid F_{a(p)kp^{n-1}}. In particular : p^2 \mid F_{a(p)p}. Wall-Sun-Sun primes A prime p'' ≠ 2, 5 is called a Fibonacci–Wieferich prime or a Wall-Sun-Sun prime if p^2 \mid F_q, where : q = p - \left(\frac \right) in which \left(\tfrac \right) is the Legendre symbol defined as: : \left(\frac{p}{5}\right) = \begin{cases} 1 & p \equiv \pm 1 \bmod 5\\ -1 & p \equiv \pm 2 \bmod 5 \end{cases} It is known that for ''p ≠ 2, 5, a''(''p) is a divisor of: : p-\left(\frac \right) = \begin{cases} p-1 & p \equiv \pm 1 \bmod 5\\ p+1 & p \equiv \pm 2 \bmod 5 \end{cases} For every prime p'' that is not a Wall-Sun-Sun prime, a(p^2) = p a(p) as illustrated in the table below: The existence of Wall-Sun-Sun primes is conjectural. Fibonacci primitive part The primitive part of the Fibonacci numbers are :1, 1, 2, 3, 5, 4, 13, 7, 17, 11, 89, 6, 233, 29, 61, 47, 1597, 19, 4181, 41, 421, 199, 28657, 46, 15005, 521, 5777, 281, 514229, 31, 1346269, 2207, 19801, 3571, 141961, 321, 24157817, 9349, 135721, 2161, 165580141, 211, 433494437, 13201, 109441, ... The product of the primitive prime factors of the Fibonacci numbers are :1, 1, 2, 3, 5, 1, 13, 7, 17, 11, 89, 1, 233, 29, 61, 47, 1597, 19, 4181, 41, 421, 199, 28657, 23, 3001, 521, 5777, 281, 514229, 31, 1346269, 2207, 19801, 3571, 141961, 107, 24157817, 9349, 135721, 2161, 165580141, 211, 433494437, 13201, 109441, 64079, 2971215073, 1103, 598364773, 15251, ... The first case of more than one primitive prime factor is 4181 = 37 × 113 for F_{19} . The primitive part has a non-primitive prime factor in some cases. The ratio between the two above sequences is :1, 1, 1, 1, 1, 4, 1, 1, 1, 1, 1, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 7, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 13, 1, 1, .... The natural numbers ''n for which F_n has exactly one primitive prime factor are :3, 4, 5, 7, 8, 9, 10, 11, 13, 14, 15, 16, 17, 18, 20, 21, 22, 23, 24, 25, 26, 28, 29, 30, 32, 33, 34, 35, 36, 38, 39, 40, 42, 43, 45, 47, 48, 51, 52, 54, 56, 60, 62, 63, 65, 66, 72, 74, 75, 76, 82, 83, 93, 94, 98, 105, 106, 108, 111, 112, 119, 121, 122, 123, 124, 125, 131, 132, 135, 136, 137, 140, 142, 144, 145, ... If and only if a prime p'' is in this sequence, then F_p is a Fibonacci prime, and if and only if 2''p is in this sequence, then L_p is a Lucas prime (where L_n is the Lucas sequence), and if and only if 2''n'' is in this sequence, then L_{2^{n-1}} is a Lucas prime. Number of primitive prime factors of F_n are :0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 1, 1, 1, 3, 1, 1, 1, 2, 1, 1, 2, 1, 2, 1, 1, 2, 2, 1, 1, 2, 1, 2, 1, 2, 2, 2, 1, 2, 1, 1, 2, 1, 1, 3, 2, 3, 2, 2, 1, 2, 1, 1, 1, 2, 2, 2, 2, 3, 1, 1, 2, 2, 2, 2, 3, 2, 2, 2, 2, 1, 1, 3, 2, 4, 1, 2, 2, 2, 2, 3, 2, 1, 1, 2, 1, 2, 2, 1, 1, 2, 2, 2, 2, 2, 3, 1, 2, 1, 1, 1, 1, 1, 2, 2, 2, ... The least primitive prime factor of F_n are :1, 1, 2, 3, 5, 1, 13, 7, 17, 11, 89, 1, 233, 29, 61, 47, 1597, 19, 37, 41, 421, 199, 28657, 23, 3001, 521, 53, 281, 514229, 31, 557, 2207, 19801, 3571, 141961, 107, 73, 9349, 135721, 2161, 2789, 211, 433494437, 43, 109441, 139, 2971215073, 1103, 97, 101, ... See also * Lucas number References External links * * [http://www.mcs.surrey.ac.uk/Personal/R.Knott/Fibonacci/fibmaths.html#fibprimes R. Knott Fibonacci primes] * Caldwell, Chris. Fibonacci number, Fibonacci prime, and Record Fibonacci primes at the Prime Pages * Factorization of the first 300 Fibonacci numbers * Factorization of Fibonacci and Lucas numbers * Small parallel Haskell program to find probable Fibonacci primes at haskell.org